A typical data storage application or service may receive requests to store data objects on behalf of one or more clients and store the data objects to one or more storage nodes. Some data storage services, which may be referred to as object-redundant storage systems, may store data objects using a redundancy technique or scheme in order to provide a higher level of durability for the stored data. For example, a data storage service may replicate the data objects it stores across two or more different storage nodes or locations to increase the likelihood that data objects will survive the failure of any given storage node or combination of nodes. In some object-redundant storage systems, each replica need not correspond to an exact copy of the object data. For example, in some object-redundant storage systems, a data object may be divided into a number of portions or “shards” according to a redundant encoding technique (e.g., erasure encoding), and each of the shards may be stored to a different storage node.
In systems in which data objects are simply replicated across multiple nodes, only one replica needs to be retrieved to retrieve the data object. However, when using a redundant encoding technique such as erasure encoding, a data object may generally be recreated from more than one, but fewer than all, of the generated shards. For example, using an erasure encoding technique that generates 20 shards from a data object, at least 10 shards may be required to recreate the data object.
While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include”, “including”, and “includes” mean including, but not limited to.